This invention relates to multicast communication in computer networks, and more particularly to optimization of a repair tree in reliable multicast protocol.
Communication between computers in a computer network can be established by one of several methods. These include unicast messaging (where a source station and a destination station exchange messages over a point to point path), broadcast communication (where a sender station transmits messages which may be received by all stations attached to the network), multicast communication (where a sender station transmits messages which may be received by a predetermined group of stations), and so forth.
Reliable point to point communication is established by use of sequence numbers in packets transmitted by a sending station, and by the receiving station transmitting an acknowledgement message (ACK message) or a negative acknowledgement message (NACK message) to the sending station. The sending station maintains a buffer containing messages which it has transmitted, and upon receipt of an ACK message indicating that a packet having a particular sequence number has been received, the sending station flushes that packet from its buffer. In the event that the sending station either receives a NACK message, or does not receive an ACK message during a certain timing period, then the sending station uses its buffer to retransmit the packet. Reliable unicast communication is established by requiring the sending station to retransmit packets until it has received an ACK message for each packet which it transmitted. An example of a reliable unicast protocol is the well known TCP/IP protocol.
A problem in reliable multicast transmission is that the sending station must respond to ACK or NACK messages transmitted by all of the receiving stations. If there are only a few receiving stations, such as for example ten (10) or so receiving stations, then receiving buffers in the transmitting station can handle the ACK or NACK traffic. However where there are hundreds of receiving stations, or thousands, or millions of receiving stations, the large number of ACK or NACK messages overwhelm the transmitting station.
It is standard engineering practice in the design of computer networks for a network manager (a person) to use a network management computer program to establish a repair tree for multicast communication. The manager assigns particular stations to be repair head stations for a particular group of receiving stations. The group of receiving stations along with the repair head station are referred to as a xe2x80x9crepair groupxe2x80x9d, with a repair head station and member stations. The repair head stations provide a solution to the problem of too many ACK or NACK messages flooding the sending station by the repair head stations receiving, and reacting to, the ACK or NACK messages transmitted by member stations of their repair group.
A problem with establishing a repair tree having a plurality of repair head stations in a reliable multicast protocol is that the locations of the member stations may not be optimum for the repair head stations established by the network manager. For example, if the repair head stations are established in the United States, and the member stations are in Europe, Japan, and South America, then retransmitting repair packets is very expensive. And the network manager may not have complete information when he establishes the repair groups, and so he does not realize that he is imposing a very expensive solution on the repair tree.
Further, a second problem with a network manager establishing a repair tree is that the topology of the repair tree cannot respond to changes in network configuration. That is, in the network links go down, new links are established, routers go down, new routers come on line, etc., and if any of these changes affects to established repair tree, then the repair tree may become inoperative.
There is needed a method and apparatus to help establish an optimum topological arrangement of a repair tree in reliable multicast transmission, especially when the receiving stations are widely separated, and to establish a simple method for the repair tree to respond to changes in the topology of the network.
Receiver stations located close together in a computer network dynamically form a multicast repair tree by a plurality of receiver stations choosing a repair head station from among the closely located receiver stations.
A receiver station calculates its distance from a repair head station by subtracting the decremented TTL value read from the IP header from the initial value of the TTL parameter carried in field TTL SCOPE of HELLO messages, transmitted by repair head stations.
Using a criteria that a closer repair head station is a more optimum repair head station, receiver stations listen to each received HELLO message, calculate the distance to the repair head station, and reaffiliate with the closest repair head station.